package 算法.leetcode.tree;

/**
 * @author lchenglong
 * @date 2022/1/24
 */
public class Fbnq {

    public static void main(String[] args) {
        // 斐波那契数列

    }

    private int  invoke(int n){
        if (n == 1 || n == 2){
            return n;
        }
        return invoke(n-1)+invoke(n-2);
    }

    private int invoke2(int n){
        if (n <=2) {
            return n;
        }
        // f(n) = f(n-1)+f(n-2)
        int[] array = new int[n];
        array[0] = 1;
        array[1] = 2;
        for (int i=2;i<n;i++){
            array[i] = array[i-1]+array[i-2];
        }
        return array[n-1];
    }
}
